package main.leetcode.clockin.July;

import java.util.Scanner;

/**
 * 378. 有序矩阵中第K小的元素
 *
 * <p>给定一个 n x n 矩阵，其中每行和每列元素均按升序排序，找到矩阵中第 k 小的元素。 请注意，它是排序后的第 k 小元素，而不是第 k 个不同的元素。
 *
 * <p>示例：matrix = [ [ 1, 5, 9], [10, 11, 13], [12, 13, 15] ], k = 8,返回 13。
 *
 * <p>提示： 你可以假设 k 的值永远是有效的，1 ≤ k ≤ n2 。
 */
public class day2 {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (true) {
            System.out.println(in.nextInt());
        }
        //        System.out.println(
        //                new day2()
        //                        .kthSmallest(
        //                                new int[][] {
        //                                    {1, 5, 9},
        //                                    {10, 11, 13},
        //                                    {12, 13, 15}
        //                                },
        //                                8));
    }

    public int kthSmallest(int[][] matrix, int k) {
        if (matrix == null || matrix[0].length == 0) {
            return -1;
        }
        int n = matrix.length;
        int l = matrix[0][0];
        int r = matrix[n - 1][n - 1];
        while (l < r) {
            int mid = l + (r - l >> 1);
            if (check(matrix, mid, n, k)) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }
        return l;
    }

    private boolean check(int[][] matrix, int mid, int n, int k) {
        // 记录左上块的个数，即大于mid的数的个数
        int cnt = 0;
        int i = 0, j = n - 1;
        while (i < n && j >= 0) {
            if (matrix[i][j] <= mid) {
                cnt += j + 1;
                ++i;
            } else {
                --j;
            }
        }
        return cnt >= k;
    }
}
